package personal.zq.practice.common.utils.leetcode.medium;

/**
 * 灯泡开关
 * 初始时有n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。
 *
 * 第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。
 *
 * 找出并返回 n轮后有多少个亮着的灯泡。
 *
 * @author zhangqing
 * @version 1.0
 * @date 2022/8/1
 */
public class BulbSwitch {
    /**
     * 思路与算法
     *
     * 如果我们将所有的灯泡从左到右依次编号为 1, 2, \cdots, n1,2,⋯,n，那么可以发现：
     *
     * 在第 ii 轮时，我们会将所有编号为 ii 的倍数的灯泡进行切换。
     *
     * 因此，对于第 kk 个灯泡，它被切换的次数恰好就是 kk 的约数个数。如果 kk 有偶数个约数，那么最终第 kk 个灯泡的状态为暗；如果 kk 有奇数个约数，那么最终第 kk 个灯泡的状态为亮。
     * 由于涉及到浮点数运算，为了保证不出现精度问题，我们可以计算n + 0.5的二次根，这样可以保证计算出来的结果向下取整在 32 位整数范围内一定正确。
     * @param n
     * @return
     */
    public int bulbSwitch(int n) {
        return (int) Math.sqrt(n + 0.5);
    }
}
